package com.hardy.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 *
 Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
 Return all such possible sentences.
 For example, given
 s ="catsanddog",
 dict =["cat", "cats", "and", "sand", "dog"].
 A solution is["cats and dog", "cat sand dog"].
 * User: Ruijie Date: 2016/8/19
 */
public class WordBreakLi {

    public static ArrayList<String> workBreak(String s,Set<String> dict){
        ArrayList<String> result=new ArrayList<String>();
        if(s==null||s.length()==0||!doWorkBreak(s,dict)){
            return result;
        }
        dfs(s,dict,0,"",result);
        return result;
    }

    private static void dfs(String s, Set<String> dict, int startIndex, String res, ArrayList<String> result) {
        System.out.println(startIndex+"    startIndex");
        if(startIndex>=s.length()){
            result.add(res);
            return;
        }
        for(int i=startIndex;i<s.length();i++){
            String curStr=s.substring(startIndex,i+1);
            if(dict.contains(curStr)){
                String newStr;
                if(res.length()>0){
                    newStr=res+" "+curStr;
                }else{
                    newStr=curStr;
                }
                dfs(s,dict,i+1,newStr,result);
            }
        }

    }

    private static boolean doWorkBreak(String s, Set<String> dict) {
        int len=s.length();
        boolean[] result=new boolean[len+1];
        result[0]=true;
        for(int i=0;i<len;i++){
            if(!result[i]){
                continue;
            }
            for(String str:dict){
                int l=str.length();
                if(i+l>len){
                    continue;
                }
                if(result[i+l]){
                    continue;
                }
                if(s.substring(i,i+l).equals(str)){
                    result[i+l]=true;
                }
            }
        }
        return result[len];
    }

    public static void main(String[] args) {
        String s="catsanddog";
        Set<String> dict=new HashSet<String>();
        dict.add("cat");
        dict.add("cats");
        dict.add("and");
        dict.add("sand");
        dict.add("dog");
        ArrayList<String> result=workBreak(s,dict);
        System.out.println(result.size());
        for(String str:result){
            System.out.print(str+"   ");
        }
    }

}
